package formal.array;

/**
 * @author DengYuan2
 * @create 2021-02-05 20:51
 */
public class M_378 {
    public static void main(String[] args) {

    }


    /**
     * 不会-直接看的大神和官方的解法中目前看得懂的一个
     *     -二分法
     *     -大神的感觉多找了很多次
     * @param matrix
     * @param k
     * @return
     */
    public static int kthSmallest(int[][] matrix, int k) {
        if (matrix==null || matrix.length==0){
            return -1;
        }
        int n= matrix.length;
        int left=matrix[0][0];
        int right = matrix[n-1][n-1];
        while (left<right){
            int mid = (left+right)/2;
            if (helper(matrix,mid,k)){
                right=mid;
            }else {
                left=mid+1;
            }

        }
        return left;
    }

    public static boolean helper(int[][] matrix,int mid,int k){
        int count = 0;
        int n=matrix.length;
        int r=n-1;
        int c=0;
        while (r>=0&&c<n){
            if (matrix[r][c]<=mid){
                count+=r+1;
                c++;
            }else {
                r--;
            }
        }
        return count>=k;
    }
}
